package net.tp.algo.graph.mst;

import net.tp.algo.graph.Graph;
import net.tp.algo.graph.UndirectedGraph;
import net.tp.struct.unionfind.UnionFind;

import java.util.*;

/**
 * User: Trung
 * Date: 5/11/13
 * Time: 11:06 AM
 */
public class Kruskal {

    /**
     *
     * @param graph Undirected weighted graph.
     * @return minimum spanning tree (expressed as graph)
     */
    public static Graph mst(Graph graph) {

        int N = graph.order();

        UndirectedGraph result = new UndirectedGraph(N);

        Set<Graph.Edge> _edges = new HashSet<>(); // remove dup edges
        for (Graph.Edge edge : graph.edges()) {
            _edges.add(edge);
        }

        List<Graph.Edge> edges = new ArrayList<>(_edges);
        Collections.sort(edges, (e1, e2) -> Double.compare(e1.weight(), e2.weight()) );

        UnionFind unionFind = new UnionFind(N);

        for (Graph.Edge edge : edges) {
            int u = edge.either();
            int w = edge.other(u);
            if (!unionFind.connected(u, w)) {
                unionFind.union(u, w);
                result.addEdge(u, w, edge.weight());
            }
        }

        return result;
    }


}
